#ifndef __Collections_LinkedList_H__
#define __Collections_LinkedList_H__

//+ Includes
#include "LinkedListNode.h"

///<summary>
/// LinkedList<T>
///</summary>
#define Collections_LinkedList(T) bindT(Collections_LinkedList,T)
#define Declare_Collections_LinkedList(T, Ti) \
	Declare_Collections_LinkedListNode(T, Ti) \
	public typedef struct _Collections_LinkedList_##T##_t { System_ObjectType(Collections_LinkedList(T), 0, 0) \
		public int_ Count; \
		public int_ Version; \
		public Collections_LinkedListNode(T) *Head; \
	} Collections_LinkedList(T); \
	Declare_DefaultCtorT(public,Collections_LinkedList,T) \
	\
	/* Forward-declare */ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddAfter)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Ti value); \
	public void spaceT(Collections_LinkedList,T,AddBefore2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Collections_LinkedListNode(T) *newNode); \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddBefore)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Ti value); \
	public void spaceT(Collections_LinkedList,T,AddFirst2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddFirst)(Collections_LinkedList(T) *t, Ti value); \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddLast)(Collections_LinkedList(T) *t, Ti value); \
	public void spaceT(Collections_LinkedList,T,AddLast2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	public void spaceT(Collections_LinkedList,T,Clear)(Collections_LinkedList(T) *t); \
	public bool spaceT(Collections_LinkedList,T,Contains)(Collections_LinkedList(T) *t, Ti value); \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,Find)(Collections_LinkedList(T) *t, Ti value); \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,FindLast)(Collections_LinkedList(T) *t, Ti value); \
	public bool spaceT(Collections_LinkedList,T,Remove)(Collections_LinkedList(T) *t, Ti value); \
	public void spaceT(Collections_LinkedList,T,Remove2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	public void spaceT(Collections_LinkedList,T,RemoveFirst)(Collections_LinkedList(T) *t); \
	public void spaceT(Collections_LinkedList,T,RemoveLast)(Collections_LinkedList(T) *t);
#define Implement_Collections_LinkedList(T, Ti) \
	Implement_Collections_LinkedListNode(T, Ti) \
	/* Forward-declare */ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,Find)(Collections_LinkedList(T) *t, Ti value); \
	private void InternalInsertNodeBefore(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Collections_LinkedListNode(T) *newNode); \
	private void InternalInsertNodeToEmptyList(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *newNode); \
	internal void InternalRemoveNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	private void ValidateNewNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	private void ValidateNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node); \
	\
	/*[ ctor ]*/ \
	public Collections_LinkedList(T) *spaceT(Collections_LinkedList,T,ctor)(Collections_LinkedList(T) *t) \
	{	baseCtor(,t,System_Object); \
		t->Count = 0; \
		t->Head = null; \
		return t; \
	} \
	\
	/*[ AddAfter ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddAfter)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Ti value) \
	{ \
		Collections_LinkedListNode(T) *newNode; \
		ValidateNode(t, node); \
		newNode = new(2,Collections_LinkedListNode(T),node->List,value); \
		InternalInsertNodeBefore(t, node->Next, newNode); \
		return newNode; \
	} \
	/*[ AddAfter ]*/ \
	public void spaceT(Collections_LinkedList,T,AddAfter2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Collections_LinkedListNode(T) *newNode) \
	{ \
		ValidateNode(t, node); \
		ValidateNewNode(t, newNode); \
		InternalInsertNodeBefore(t, node->Next, newNode); \
		newNode->List = t; \
	} \
	\
	/*[ AddBefore ]*/ \
	public void spaceT(Collections_LinkedList,T,AddBefore2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Collections_LinkedListNode(T) *newNode) \
	{ \
		ValidateNode(t, node); \
		ValidateNewNode(t, newNode); \
		InternalInsertNodeBefore(t, node, newNode); \
		newNode->List = t; \
		if (node == t->Head) \
		{ \
			t->Head = newNode; \
		} \
	} \
	/*[ AddBefore ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddBefore)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Ti value) \
	{ \
		Collections_LinkedListNode(T) *newNode; \
		ValidateNode(t, node); \
		newNode = new(2,Collections_LinkedListNode(T),node->List,value); \
		InternalInsertNodeBefore(t, node, newNode); \
		if (node == t->Head) \
		{ \
			t->Head = newNode; \
		} \
		return newNode; \
	} \
	\
	/*[ AddFirst ]*/ \
	public void spaceT(Collections_LinkedList,T,AddFirst2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		ValidateNewNode(t, node); \
		if (t->Head == null) \
		{ \
			InternalInsertNodeToEmptyList(t, node); \
		} \
		else \
		{ \
			InternalInsertNodeBefore(t, t->Head, node); \
			t->Head = node; \
		} \
		node->List = t; \
	} \
	/*[ AddFirst ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddFirst)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		Collections_LinkedListNode(T) *newNode = new(2,Collections_LinkedListNode(T),t,value); \
		if (t->Head == null) \
		{ \
			InternalInsertNodeToEmptyList(t, newNode); \
			return newNode; \
		} \
		InternalInsertNodeBefore(t, t->Head, newNode); \
		t->Head = newNode; \
		return newNode; \
	} \
	\
	/*[ AddLast ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,AddLast)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		Collections_LinkedListNode(T) *newNode = new(2,Collections_LinkedListNode(T),t,value); \
		if (t->Head == null) \
		{ \
			InternalInsertNodeToEmptyList(t, newNode); \
			return newNode; \
		} \
		InternalInsertNodeBefore(t, t->Head, newNode); \
		return newNode; \
	} \
	/*[ AddLast ]*/ \
	public void spaceT(Collections_LinkedList,T,AddLast2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		ValidateNewNode(t, node); \
		if (t->Head == null) \
		{ \
			InternalInsertNodeToEmptyList(t, node); \
		} \
		else \
		{ \
			InternalInsertNodeBefore(t, t->Head, node); \
		} \
		node->List = t; \
	} \
	\
	/*[ Clear ]*/ \
	public void spaceT(Collections_LinkedList,T,Clear)(Collections_LinkedList(T) *t) \
	{ \
		Collections_LinkedListNode(T) *head = t->Head; \
		while (head != null) \
		{ \
			Collections_LinkedListNode(T) *node2 = head; \
			head = head->Next; \
			delete(node2); \
		} \
		delete(t->Head); t->Head = null; \
		t->Count = 0; \
		t->Version++; \
	} \
	\
	/*[ Contains ]*/ \
	public bool spaceT(Collections_LinkedList,T,Contains)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		return (spaceT(Collections_LinkedList,T,Find)(t, value) != null); \
	} \
	\
	/*[ Find ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,Find)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		Collections_LinkedListNode(T) *head = t->Head; \
		Collections_EqualityComparer(T) *comparer = getsT(Collections_EqualityComparer,T,Default); \
		if (head != null) \
		{ \
			if (value != null) \
			{ \
				do \
				{ \
					if (vcallT(Collections_EqualityComparer,T,t,Equals)((System_Object *)comparer, head->Value, value) == true) \
					{ \
						return head; \
					} \
					head = head->Next; \
				} \
				while (head != t->Head); \
			} \
			else \
			{ \
				do \
				{ \
					if (head->Value == null) \
					{ \
						return head; \
					} \
					head = head->Next; \
				} \
				while (head != t->Head); \
			} \
		} \
		return null; \
	} \
	\
	/*[ FindLast ]*/ \
	public Collections_LinkedListNode(T) *spaceT(Collections_LinkedList,T,FindLast)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		Collections_EqualityComparer(T) *comparer; \
		if (t->Head != null) \
		{ \
			Collections_LinkedListNode(T) *prev = t->Head->Prev; \
			Collections_LinkedListNode(T) *node2 = prev; \
			comparer = getsT(Collections_EqualityComparer,T,Default); \
			if (node2 != null) \
			{ \
				if (value != null) \
				{ \
					do \
					{ \
						if (vcallT(Collections_EqualityComparer,T,t,Equals)((System_Object *)comparer, node2->Value, value) == true) \
						{ \
							return node2; \
						} \
						node2 = node2->Prev; \
					} \
					while (node2 != prev); \
				} \
				else \
				{ \
					do \
					{ \
						if (node2->Value == null) \
						{ \
							return node2; \
						} \
						node2 = node2->Prev; \
					} \
					while (node2 != prev); \
				} \
			} \
		} \
		return null; \
	} \
	\
	/*[ InternalInsertNodeBefore ]*/ \
	private void InternalInsertNodeBefore(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node, Collections_LinkedListNode(T) *newNode) \
	{ \
		newNode->Next = node; \
		newNode->Prev = node->Prev; \
		node->Prev->Next = newNode; \
		node->Prev = newNode; \
		t->Version++; \
		t->Count++; \
	} \
	\
	/*[ InternalInsertNodeToEmptyList ]*/ \
	private void InternalInsertNodeToEmptyList(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *newNode) \
	{ \
		newNode->Next = newNode; \
		newNode->Prev = newNode; \
		t->Head = newNode; \
		t->Version++; \
		t->Count++; \
	} \
	\
	/*[ InternalRemoveNode ]*/ \
	internal void InternalRemoveNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		if (node->Next == node) \
		{ \
			t->Head = null; \
		} \
		else \
		{ \
			node->Next->Prev = node->Prev; \
			node->Prev->Next = node->Next; \
			if (t->Head == node) \
			{ \
				t->Head = node->Next; \
			} \
		} \
		delete(node); \
		t->Count--; \
		t->Version++; \
	} \
	\
	/*[ Remove ]*/ \
	public bool spaceT(Collections_LinkedList,T,Remove)(Collections_LinkedList(T) *t, Ti value) \
	{ \
		Collections_LinkedListNode(T) *node = spaceT(Collections_LinkedList,T,Find)(t, value); \
		if (node != null) \
		{ \
			InternalRemoveNode(t, node); \
			return true; \
		} \
		return false; \
	} \
	/*[ Remove ]*/ \
	public void spaceT(Collections_LinkedList,T,Remove2)(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		ValidateNode(t, node); \
		InternalRemoveNode(t, node); \
	} \
	\
	/*[ RemoveFirst ]*/ \
	public void spaceT(Collections_LinkedList,T,RemoveFirst)(Collections_LinkedList(T) *t) \
	{ \
		if (t->Head == null) \
		{ \
			throw(InvalidOperationException, L"LinkedListEmpty"); \
		} \
		InternalRemoveNode(t, t->Head); \
	} \
	\
	/*[ RemoveLast ]*/ \
	public void spaceT(Collections_LinkedList,T,RemoveLast)(Collections_LinkedList(T) *t) \
	{ \
		if (t->Head == null) \
		{ \
			throw(InvalidOperationException, L"LinkedListEmpty"); \
		} \
		InternalRemoveNode(t, t->Head->Prev); \
	} \
	\
	/*[ ValidateNewNode ]*/ \
	private void ValidateNewNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		if (node == null) throw(ArgumentNullException, L"node"); \
		if (node->List != null) throw(InvalidOperationException, L"LinkedListNodeIsAttached"); \
	} \
	\
	/*[ ValidateNode ]*/ \
	private void ValidateNode(Collections_LinkedList(T) *t, Collections_LinkedListNode(T) *node) \
	{ \
		if (node == null) throw(ArgumentNullException, L"node"); \
		if (node->List != t) throw(InvalidOperationException, L"ExternalLinkedListNode"); \
	}

#endif /* __Collections_LinkedList_H__ */